#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <thread>
#include <numeric>

template <typename Iterator, typename T>
struct accumulate_block
{
    void operator()(Iterator first, Iterator last, T& value) 
    {
        value = std::accumulate(first, last, value);
    }
};

template <typename Iterator, typename T>
T _parallel_accumulate(Iterator first, Iterator last, T init, std::random_access_iterator_tag)
{
    typedef typename std::iterator_traits<Iterator>::difference_type diff_type;
    diff_type total_cnt = std::distance(first, last);   

    int num_threads = std::thread::hardware_concurrency() == 0 ? 2 : std::thread::hardware_concurrency();
    if (num_threads > total_cnt) return std::accumulate(first, last, init);
    std::vector<T> results(num_threads);
    std::vector<std::thread> threads(num_threads - 1);
    diff_type block_size = total_cnt / num_threads;
    Iterator block_first = first;
    for (int i = 0; i < num_threads - 1; i++) {
        Iterator block_end = block_first + block_size;
        threads[i] = std::thread(accumulate_block<Iterator, T>(), block_first, block_end, std::ref(results[i]));
        block_first = block_end;
    }
    results[num_threads - 1] = std::accumulate(block_first, last, results[num_threads - 1]);
    for (auto& thread : threads) thread.join();
    return std::accumulate(results.begin(), results.end(), init);
}

template <typename Iterator, typename T>
T _parallel_accumulate(Iterator first, Iterator last, T init, std::input_iterator_tag)
{
    return std::accumulate(first, last, init);
}

template <typename Iterator, typename T>
T parallel_accumulate(Iterator first, Iterator last, T init) 
{
    typedef typename std::iterator_traits<Iterator>::iterator_category category;
    return _parallel_accumulate(first, last, init, category());
}

int main(int argc, char* argv[]) {
    if (argc < 2) return 0;
    long cnt = atol(argv[1]);
    std::vector<long> test(cnt, 1L);
    long res = 0;
    std::cout << "单线程测试:" << std::endl;
    auto start = std::chrono::high_resolution_clock::now();
    // 单线程
    res = std::accumulate(test.begin(), test.end(), 0L);
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> elapsed = end-start;
    std::cout << "Waited " << elapsed.count() << " ms\n";
    std::cout << res << std::endl;

    std::cout << "多线程测试:" << std::endl;
    start = std::chrono::high_resolution_clock::now();
    // 单线程
    res = parallel_accumulate(test.begin(), test.end(), 0L);
    end = std::chrono::high_resolution_clock::now();
    elapsed = end-start;
    std::cout << "Waited " << elapsed.count() << " ms\n";
    std::cout << res << std::endl;

    return 0;
}
// 测试机腾讯云2核8G, 当求和数组大小超过100000时才有性能提升, 最高提升 20% 的速度, 理论上提升 50% 性能
// root@VM-0-6-ubuntu:~/concurrency-learn/build# ./accumulate_test 10
// 单线程测试:
// Waited 0.000431 ms
// 10
// 多线程测试:
// Waited 0.124452 ms
// 10
// root@VM-0-6-ubuntu:~/concurrency-learn/build# ./accumulate_test 100
// 单线程测试:
// Waited 0.001273 ms
// 100
// 多线程测试:
// Waited 0.26719 ms
// 100
// root@VM-0-6-ubuntu:~/concurrency-learn/build# ./accumulate_test 1000
// 单线程测试:
// Waited 0.009487 ms
// 1000
// 多线程测试:
// Waited 0.228769 ms
// 1000
// root@VM-0-6-ubuntu:~/concurrency-learn/build# ./accumulate_test 10000
// 单线程测试:
// Waited 0.100097 ms
// 10000
// 多线程测试:
// Waited 0.192881 ms
// 10000
// root@VM-0-6-ubuntu:~/concurrency-learn/build# ./accumulate_test 100000
// 单线程测试:
// Waited 0.7689 ms
// 100000
// 多线程测试:
// Waited 0.739425 ms
// 100000
// root@VM-0-6-ubuntu:~/concurrency-learn/build# ./accumulate_test 1000000
// 单线程测试:
// Waited 7.57136 ms
// 1000000
// 多线程测试:
// Waited 6.22335 ms
// 1000000
// root@VM-0-6-ubuntu:~/concurrency-learn/build# ./accumulate_test 10000000
// 单线程测试:
// Waited 73.9563 ms
// 10000000
// 多线程测试:
// Waited 60.1964 ms
// 10000000
// root@VM-0-6-ubuntu:~/concurrency-learn/build# ./accumulate_test 100000000
// 单线程测试:
// Waited 746.366 ms
// 100000000
// 多线程测试:
// Waited 586.458 ms
// 100000000
// root@VM-0-6-ubuntu:~/concurrency-learn/build# ./accumulate_test 200000000
// 单线程测试:
// Waited 1486.14 ms
// 200000000
// 多线程测试:
// Waited 1180.44 ms
// 200000000
// root@VM-0-6-ubuntu:~/concurrency-learn/build# ./accumulate_test 300000000
// 单线程测试:
// Waited 2225.96 ms
// 300000000
// 多线程测试:
// Waited 1757.8 ms
// 300000000